package com.chj.leetcode.tijie0to50;

public class Code31_NextPermutation {
	public void nextPermutation(int[] nums) {
		if (nums == null || nums.length == 0)
			return;
		int firstIndex = -1;
		for (int i = nums.length - 2; i >= 0; i--) {
			if (nums[i] < nums[i + 1]) {
				firstIndex = i;
				break;
			}
		}
		if (firstIndex == -1) {
			reverse(nums, 0, nums.length - 1);
			return;
		}
		int secondIndex = -1;
		for (int i = nums.length - 1; i >= 0; i--) {
			if (nums[i] > nums[firstIndex]) {
				secondIndex = i;
				break;
			}
		}

		swap(nums, firstIndex, secondIndex);
		reverse(nums, firstIndex + 1, nums.length - 1);
		return;
	}

	public void reverse(int[] chs, int l, int r) {
//		char[] chs = str.toCharArray();
//		int l = 0;
//		int r = chs.length - 1;
		while (l < r) {
			int tmp = chs[l];
			chs[l++] = chs[r];
			chs[r--] = tmp;
		}
//		return String.valueOf(chs);
	}

//	private void reverse(int[] nums, int i, int j) {
//		while (i < j) {
//			swap(nums, i++, j--);
//		}
//	}
//
	private void swap(int[] nums, int i, int j) {
		int tmp = nums[i];
		nums[i] = nums[j];
		nums[j] = tmp;
	}

//	作者：powcai
//	链接：https:// leetcode-cn.com/problems/next-permutation/solution/xia-yi-ge-pai-lie-by-powcai/
//	来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

//	func nextPermutation(nums []int) {
//		if len(nums) <= 1 {
//			return
//		}
//
//		i, j, k := len(nums)-2, len(nums)-1, len(nums)-1
//
//		// find: A[i]<A[j]
//		for i >= 0 && nums[i] >= nums[j] {
//			i--
//			j--
//		}
//
//		if i >= 0 { // 不是最后一个排列
//			// find: A[i]<A[k]
//			for nums[i] >= nums[k] {
//				k--
//			}
//			// swap A[i], A[k]
//			nums[i], nums[k] = nums[k], nums[i]
//		}
//
//		// reverse A[j:end]
//		for i, j := j, len(nums)-1; i < j; i, j = i+1, j-1 {
//			nums[i], nums[j] = nums[j], nums[i]
//		}
//	}
//
//
//	作者：imageslr
//	链接：https://leetcode-cn.com/problems/next-permutation/solution/xia-yi-ge-pai-lie-suan-fa-xiang-jie-si-lu-tui-dao-/
//	来源：力扣（LeetCode）
//	著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

	public static void main(String[] args) {
		{
			Code31_NextPermutation c31 = new Code31_NextPermutation();
			int[] nums = new int[] { 1, 2, 3, 4, 6, 5 };
			c31.nextPermutation(nums);
			System.out.println(nums);
		}

		{
			Code31_NextPermutation c31 = new Code31_NextPermutation();
			int[] nums = new int[] { 6, 5, 4, 3, 2, 1 };
			c31.nextPermutation(nums);
			System.out.println(nums);
		}
	}
}
